8.4.3. İkili Arama Ağacında Arama Algoritmaları

İkili arama ağacı üzerinde arama, onun en önemli yanıdır. Dengeli denilebilecek bir ikili arama ağacında arama işlemi O(LogN) karmaşıklığında gerçekleştirilir. Dolayısıyla ikili ağaçların bu kadar yaygın kullanılmasının nedeni bu özelliktir. Örneğin 1 milyon tane kayıtın olduğu bir veritabanı uygulamasında, arama işlemi, doğrusal liste kullanıldığında 1 milyon çevrim, ikili arama ağacı kullanıldığında, yaklaşık, log1milyon» 20 'den 20 çevrim gerektirir.

Aşağıda arama algoritmasının kaba-kodu verilmiştir. Arama algoritması dolaşma algoritmasından farklılık gösterir. Çünkü dolaşma algoritmasında tüm düğümlerin ziyaret edilmesi gerekir. Ancak arama algoritmasına arananın bulunduğu yere doğru ilerlenmesi yeterlidir. Yani kendi silsilesinde yoksa ağaçta da yoktur denilebilir. Aşağıdaki kaba-kodu verilen arama algoritması aranan ağaçta birden çok varsa ilk bulduğu yerin adresini gönderir. Hepsinin aranıp bulunması için üzerinde değişiklik yapılmalıdır!

Fonksiyon-8.4. İkili ağaçında üzerinde arama fonksiyonu

/* Ağaç üzerinde bir kayıt arama */
AGAC2 *ara(AGAC2 *agacKok, int aranan) {
            while(agacKok!=NULL && agacKok->bilgi!=aranan) {
                  if(aranan <= agacKok->bilgi)
                         agacKok=agacKok->sol;
                  else
                         agacKok=agacKok->sag;
             }
             return agacKok;
}